|
In mathematics, a distance-regular graph is a regular graph such that for any two vertices ''v'' and ''w'', the number of vertices at distance ''j'' from ''v'' and at distance ''k'' from ''w'' depends only upon ''j'', ''k'', and ''i = d(v, w)''. By considering the special case ''k = 1'', one sees that in a distance-regular graph, for any two vertices ''v'' and ''w'' at distance ''i'', the number of neighbors of ''w'' that are at distance ''j'' from ''v'' is the same. Conversely, it turns out that this special case implies the full definition of distance-regularity.〔 A.E. Brouwer, A.M. Cohen, and A. Neumaier (1989), ''Distance Regular Graphs''. Berlin, New York: Springer-Verlag. ISBN 3-540-50619-5, ISBN 0-387-50619-5〕 Therefore, an equivalent definition is that a distance-regular graph is a regular graph for which there exist integers bi,ci,i=0,...,d such that for any two vertices x,y with y in Gi(x), there are exactly bi neighbors of y in Gi-1(x) and ci neighbors of y in Gi+1(x), where Gi(x) is the set of vertices y of G with d(x,y)=i (Brouwer et al., p. 434). The array of integers characterizing a distance-regular graph is known as its intersection array. Every distance-transitive graph is distance regular. Indeed, distance-regular graphs were introduced as a combinatorial generalization of distance-transitive graphs, having the numerical regularity properties of the latter without necessarily having a large automorphism group. A distance-regular graph with diameter 2 is strongly regular, and conversely (unless the graph is disconnected). ==Intersection numbers== It is usual to use the following notation for a distance-regular graph ''G''. The number of vertices is ''n''. The number of neighbors of ''w'' (that is, vertices adjacent to ''w'') whose distance from ''v'' is ''i'', ''i'' + 1, and ''i'' − 1 is denoted by ''ai'', ''bi'', and ''ci'', respectively; these are the intersection numbers of ''G''. Obviously, ''a''0 = 0, ''c''0 = 0, and ''b''0 equals ''k'', the degree of any vertex. If ''G'' has finite diameter, then ''d'' denotes the diameter and we have ''bd'' = 0. Also we have that ''ai+bi+ci= k'' The numbers ''ai'', ''bi'', and ''ci'' are often displayed in a three-line array : called the intersection array of ''G''. They may also be formed into a tridiagonal matrix : called the intersection matrix. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Distance-regular graph」の詳細全文を読む スポンサード リンク
|